A storage server is a special-purpose processing system which is used to store and retrieve data on behalf of one or more client processing systems (“clients”). A storage server can be used for many different purposes, such as to provide multiple users with access to shared data or to back up mission critical data.
A file server is one example of a storage server. A file server operates on behalf of one or more clients to store and manage shared files in a set of mass storage devices, such as magnetic or optical storage based disks or tapes. The mass storage devices are typically organized into one or more volumes of Redundant Array of Inexpensive Disks (RAID).
A file server typically includes a file system, which is software that keeps track of all of the data stored by the file server and manages read/write operations on the data. The term “file system” can also be used to refer to the actual structure of the stored data. The files within a file server are generally stored within a hierarchy of directories. A directory is simply a software-based entity which can contain information, such as one or more files, other directories and/or other data, and which is used to organize stored information.
Any data stored in a computer system has the potential to become corrupted, including the data which represents the directory structure in a file system. Undetected errors in the directory structure of a storage server can cause critical loss of data and/or downtime. Therefore, in storage servers, particularly those which store data on a very large-scale, it is desirable to have a way to test the directories in the file system for errors, to allow correction of such errors before significant damage can occur.
A storage server, such as a file server, can keep track of stored data by using inodes. An inode is a data structure, stored in an inode file, that keeps track of which logical blocks of data in a storage pool are used to store a file. In certain file servers, each stored file is represented by a corresponding inode. A directory is, at its most fundamental level, a mapping between filenames and inode indices.
For example, if a user has created a file called “hello” within a directory and later tries to read that file, the file system has to know that “hello” is stored in, for example, inode #36 in the inode file. Likewise, if the user creates a subdirectory called “private”, then the file system has to know that the subdirectory is stored in, for example, inode #122 in the inode file. The directory structure maintains these mappings. A file server generally includes many such directories.
In one prior art file server, each directory is stored in the form of one or more 4-kbyte blocks, stored in various places in the storage pool. To create the directory structure, each of those 4-kbyte blocks are divided into two 2-kbyte “segments”. There are two types of segment: name segments and tree segments. Each directory has at least one name segment and at least one tree segment. Name segments contain the basic mappings between filenames and inode numbers, while tree segments are used to accelerate filename lookups. Each tree segment points to some number of name segments and, in some cases, to one or more other tree segments. Two 2-kbyte segments fit into every 4-kbyte block. Note the distinction here between a directory and the information (e.g., files) contained in the directory: what is being described here is the manner in which the directory itself is represented in the storage pool, not the information contained in the directory.
A directory has at least one tree segment and at least one name segment. The tree segment or segments of the directory form a hierarchical structure referred to as a radix tree. The radix tree is a device used to accelerate lookups of filenames in the directory. As shown in example of FIG. 1, multiple tree segments 2 can make up a radix tree 1 of a directory. The radix tree of a directory always includes at least a root tree segment T1 and may also include one or more other tree segments 2. The root tree segment T1 references the other tree segments 2 either directly or indirectly. Each tree segment 2 refers to some number of name segments (not shown).
A directory can become very large, so as to be represented on disk by a very large radix tree with many segments. Large directories can present problems, however, for purposes of directory testing and validation, especially in a very large storage pool. One known prior art file server uses a directory structure such as described above (radix trees of name segments and tree segments) and includes a software utility to perform testing and validation of directories. The prior art testing algorithm generally batches together all of the name segments under a given tree segment, performs validation on those names, then repeats the process for each tree segment in the directory, and then further repeats this process for each directory in the storage pool.
One problem with this approach is that many directories are too large to store in main memory in their entirety (i.e., including all of their name segments). Consequently, many disk read operations (“I/Os”) are required to access the directory information (segments) on disk during directory validation. Disk I/Os tend to involve high latency in comparison to accessing main memory. This problem is exacerbated by very large directories and very large storage pools. As a result of disk I/O latency, the process of testing and validating all directories can take hours or even days for a very large storage pool.